package huffmanTree.std01;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 实现：
 * 【13，7，8，3，29，6，1】转成哈夫曼树
 */
public class HuffmanTree {
    /**
     * 实现操作逻辑：
     * 1.将给到的数组转成node 节点转到list
     * 2.将node 从小到大排序
     * 3.取出 最小的两个节点 相加 然后将值放入到数组 并删除两个节点 并重复2 3 操作
     * 4.当数组里就剩一个节点时候 说明哈夫曼树已经构造完毕
     */
    public static void main(String[] args) {
        int[] a =  {13,7,8,3,29,6,1};
        List<Node> nodes = getNodes(a);
        Node huffManRoot = getHuffManRoot(nodes);
        preOut(huffManRoot);
    }

    /**
     * 前序遍历 根 左 右
     * @param root
     */
    public static void preOut(Node root){
        System.out.print(root.weight + "   ");
        if(null != root.left){
            preOut(root.left);
        }
        if (null != root.right){
            preOut(root.right);
        }
    }

    /**
     * 获取 huffman 根节点
     * @param nodes 节点
     * @return 根节点
     */
    public static Node getHuffManRoot(List<Node> nodes){
        while (nodes.size()>1){
            //将node 从小到大排序
            Collections.sort(nodes);
            //取出 最小的两个节点
            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);
           // 相加 然后将值放入到数组 并删除两个节点 并重复2 3 操作
            Node newNode = new Node(leftNode.weight+rightNode.weight);
            newNode.left = leftNode;
            newNode.right = rightNode;
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            nodes.add(newNode);
        }
        return nodes.get(0);
    }

    /**
     * 将数组 转为list
     * @param a 数组
     * @return list<Node>
     */
    public static List<Node> getNodes(int[] a){
        List<Node> nodes = new ArrayList<>();
        if (a.length > 0 ) {
            for (Integer  i : a) {
                Node node = new Node(i);
                nodes.add(node);
            }
        }
        return nodes;
    }

   static class Node implements Comparable<Node>{
        int weight;//权值
        Node left;
        Node right;
        public Node(int weight) {
            this.weight = weight;
        }

        @Override
        public int compareTo(Node o) {
            return weight - o.weight ;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "weight=" + this.weight +
                    '}';
        }
    }

}
